package lc_2719_统计整数数目;

public class Solution {

	int floor[], ceil[], n, min, max;

	int mod = (int) 1e9 + 7;

	Integer[][][] dp;

	public int count(String num1, String num2, int min_sum, int max_sum) {
		min = min_sum;
		max = max_sum;
		n = num2.length();
		floor = g(num1, n);
		ceil = g(num2, n);
		dp = new Integer[n][4][500];
		return f(0, 3, 0);
	}

	private int f(int index, int bound, int tot) {
		if (index == n) {
			return min <= tot && tot <= max ? 1 : 0;
		}
		if (tot > max) {
			return 0;
		}
		if (dp[index][bound][tot] != null) {
			return dp[index][bound][tot];
		}
		int L = (bound & 1) == 1 ? floor[index] : 0;
		int R = (bound & 2) == 2 ? ceil[index] : 9;
		long ans = 0;
		for (int i = L; i <= R; i++) {
			int next_bound = ((bound & 1) == 1 && i == L ? 1 : 0) | ((bound & 2) == 2 && i == R ? 2 : 0);
			ans += f(index + 1, next_bound, tot + i);
			ans %= mod;
		}
		dp[index][bound][tot] = (int) (ans % mod);
		return dp[index][bound][tot];
	}

	private int[] g(String num, int n) {
		int[] nums = new int[n];
		for (int j = num.length() - 1, i = n - 1; j > -1; j--, i--) {
			nums[i] = num.charAt(j) - '0';
		}
		return nums;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		System.out.println(so.count("1", "12", 1, 8));
	}

}